package org.loneranger.sword.offer24;

/**
 * 反转链表
 *
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 * 作者：Krahets
 * 链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/9pdjbm/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author LoneRanger
 * @version 1.0
 */
public class Offer24 {
	public static void main(String[] args) {
		ListNode n1 = new ListNode(1);
		ListNode n2 = new ListNode(2);
		ListNode n3 = new ListNode(3);
		ListNode n4 = new ListNode(4);
		ListNode n5 = new ListNode(5);
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		System.out.println(new Solution_3().reverseList(n1).val);
	}
}

class Solution {
	public ListNode reverseList(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode qian = null;

		while (true) {
			if (head == null) {
				break;
			}
			if (head.next == null) {
				head.next = qian;
				qian = head;
				break;
			}
			ListNode n1 = head;
			ListNode n2 = head.next;
			head = n2.next;
			n1.next = qian;
			n2.next = n1;
			qian = n2;
		}
		return qian;
	}
}

class Solution_1 {
	public ListNode reverseList(ListNode head) {
		ListNode p = null;
		ListNode h = null;
		while (head != null) {
			h = head;
			head = head.next;
			h.next = p;
			p = h;
		}
		return p;
	}
}

class Solution_2 {
	public ListNode reverseList(ListNode 等待处理的) {
		ListNode 返回的头 = null;
		while (等待处理的 != null) {
			ListNode head = 等待处理的;
			等待处理的 = 等待处理的.next;
			head.next = null;
			if (返回的头 == null) {
				返回的头 = head;
			} else {
				head.next = 返回的头;
				返回的头 = head;
			}
		}
		return 返回的头;
	}
}

class Solution_3 {
	public ListNode reverseList(ListNode head) {
		return recur(head, null);    // 调用递归并返回
	}
	private ListNode recur(ListNode cur, ListNode pre) {
		if (cur == null) {
			return pre; // 终止条件
		}
		ListNode res = recur(cur.next, cur);  // 递归后继节点
		cur.next = pre;              // 修改节点引用指向
		return res;                  // 返回反转链表的头节点
	}
}


